package com.datastructures.linkedList;

/**
 * @author MaoLin Wang
 * @date 2019/10/2015:33
 */
public class Joseful {
    public static void main(String[] args) {

        CircleSingleLinkedList c = new CircleSingleLinkedList();
        c.add(4);
        c.printData();
     //   c.countBoy(1,4,50);
    }
}

//创建环形单向链表
class CircleSingleLinkedList {
    /**
     * 创建一个first节点，无编号
     */
    private Boy first = new Boy(-1);

    /**
     * 添加节点，构建环形链表
     *
     * @param nums
     */
    public void add(int nums) {
        if (nums < 1) {
            System.out.println("num不正确");
            return;
        }
        Boy cur = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                //构建第一个节点
                first = boy;
                first.next = first;//构成环
                cur = first;//让cur指向第一个节点
            } else {
                cur.next = boy;//当前节点的下一个节点指向新节点
                boy.next = first;//新节点的next指向头部
                cur = boy;//后移cur
            }
        }
    }

    public void printData() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy cur = first;
        while (true) {
            System.out.println(cur);
            if (cur.next == first) {//已到最后一个几点
                break;
            }
            cur = cur.next;
        }
    }


    /**
     * 根据用户的输入，计算出出队顺序
     *
     * @param start    从第几个小孩开始数数
     * @param countNum 数几下
     * @param nums     最初有多少个小孩在圈中
     */
    public void countBoy(int start, int countNum, int nums) {
        if (first == null || start < 1 || start > nums) {
            System.out.println("数据不合理");
            return;
        }
        Boy helper = first;
        while (true) {
            if (helper.next == first) {
                break;
            }
            helper = helper.next;
        }
        //报数前，让first和helper移动k-1次
        for (int j=0;j<start-1;j++){
            first=first.next;
            helper=helper.next;
        }
        //当小孩报数时，让first和cur指针同时移动m-1次
        while (true){
            //直到圈中只有一个节点结束
            if (helper==first){
                break;
            }
            //让两个指针同时移动countNum-1次
            for (int j=0;j<countNum-1;j++){
                first=first.next;
                helper=helper.next;
            }
            //first指向的接地那就是要出队的节点
            System.out.println("出圈小孩为："+first.id);
            //将first指向小结节点出圈
            first=first.next;
            helper.next=first;
        }
        System.out.println("最后剩下的孩子为:"+first.id);

    }
}

//创建一个Boy类，表示一个节点
class Boy {
    public int id;
    public Boy next;//指向下一个节点

    public Boy(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "id=" + id +

                '}';
    }
}